def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
    for cents in range(change + 1):
        coinCount = cents
        newCoin = 1  # 初始化新加硬币
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newCoin = j  # 对应最小数量，所减的硬币
        minCoins[cents] = coinCount
        coinsUsed[cents] = newCoin  #记录本步骤所加的一个硬币
    return minCoins[change]


def printCoins(coubsUsed, change):
    coin = change
    while coin > 0:
        thisCoin = coubsUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin


amnt = 63
clist = [1, 5, 10, 21, 25]
coinsUsed = [0] * (amnt + 1)
coinCount = [0] * (amnt + 1)
print(amnt)
print(dpMakeChange(clist, amnt, coinCount, coinsUsed))
printCoins(coinsUsed, amnt)
print(coinsUsed)
